# 使用排序+贪心求最小建设基站数量
def minStations(ranges: list[list[int]]) -> int:
    # 边界判断：一个需求都没有那就返回0
    if not ranges: 
        return 0

    # 将需求按左边界+右边界排序
    ranges.sort()

    # 每一座基站在尽可能多覆盖需求的前提下尽可能放右边，
    # 用minRight维护当前基站可以建设的最远（右）位置
    n, minRight = 1, ranges[0][1]
    for left, right in ranges:
        if left > minRight:
            n += 1
            minRight = right
        else:
            minRight = min(minRight, right)

    return n

ranges = [[1, 4], [2, 3], [4, 5]]
n = minStations(ranges)
print('基站数目:', n)
